package dom.xpath.query.xpath.locpath;

import dom.xpath.data.Data;
import dom.xpath.index.Index;
import dom.xpath.query.EvalException;
import dom.xpath.query.xpath.XPContext;
import dom.xpath.query.xpath.expr.Expression;
import dom.xpath.query.xpath.expr.Filter;
import dom.xpath.query.xpath.expr.InterSect;
import dom.xpath.query.xpath.expr.Path;
import dom.xpath.query.xpath.internal.IndexMatch;
import dom.xpath.query.xpath.values.Comp;
import dom.xpath.query.xpath.values.Literal;
import dom.xpath.query.xpath.values.NodeSet;
import dom.xpath.util.IntList;
import static dom.xpath.query.xpath.XPText.*;

/**
 * LocationPath (absolute or relative).
 * 
 * @author Workgroup DBIS, University of Konstanz 2005-07, ISC License
 * @author Tim Petrowsky
 */
public abstract class LocationPath extends Expression {
  /** List of location steps. */
  public Steps steps = new Steps();

  @Override
  public abstract NodeSet eval(final XPContext ctx) throws EvalException;

  @Override
  public final Expression compile(final XPContext ctx) throws EvalException {
    // At this point a data reference has to be available;
    if(ctx.local == null) throw new EvalException(NODATA);

    // replacing self::node() with child::text() for possible index integration
    if(ctx.leaf && steps.size() == 1 && steps.get(0).simple(Axis.SELF)) {
      steps.set(0, Axis.get(Axis.CHILD, TestNode.TEXT));
      ctx.compInfo(OPTTEXT);
    }

    // check if all steps yield results
    if(!steps.compile(ctx) || steps.emptyPath(ctx)) return new NodeSet(ctx);

    // remove superfluous self axes
    steps.mergeSelf(ctx);

    // merge descendant and child steps
    steps.mergeDescendant(ctx);

    // check with paths if the available indexes can be applied
    Expression result = this;

    for(int i = 0; i < steps.size(); i++) {
      final Step step = steps.get(i);
      final Preds preds = step.preds;

      // skip optimization if no preds are specified or if a pos.pred is found
      // <CG> XPath/Path optimization: enough to check first predicate?
      if(preds.size() == 0 || step.posPred() > 0) continue;
      
      // don't optimize non-forward axes
      if(invertAxis(step.axis) == null) continue;

      // find predicate with lowest number of occurrences
      int min = Integer.MAX_VALUE;
      int minP = -1; 
      for(int p = 0; p < preds.size(); p++) {
        final Pred pred = preds.get(p);
        final int nrIDs = pred.indexSizes(ctx, step, min);

        if(min > nrIDs) {
          if(nrIDs == 0) {
            ctx.compInfo(OPTLOC);
            return new NodeSet(ctx);
          }
          min = nrIDs;
          minP = p;
        }
      }
      if(min == Integer.MAX_VALUE) continue;
      // ..what is the optimal maximum for index access?
      if(this instanceof RelativeLocationPath && min > 100) continue;
      
      // predicates that are optimized to use index and results of index queries
      final IntList oldPreds = new IntList();
      Expression indexArg = null;

      for(int p = 0; p < preds.size(); p++) {
        final Pred pred = preds.get(p);

        if(p == minP && indexArg == null) {
          oldPreds.add(p);
          indexArg = pred.indexEquivalent(ctx, step);
        }
      }

      // hold all steps following this step
      final LocationPath oldPath = new RelativeLocationPath();
      for(final int j = i + 1; j < steps.size();) {
        final Step oldStep = steps.get(j);
        steps.remove(j);
        oldPath.steps.add(oldStep);
      }

      // hold the part of the path we want to invert.
      // suggestion: all forward steps without predicates in front of the index
      final LocationPath invPath = new RelativeLocationPath();

      boolean indexMatch = true;
      for(int j = i; j >= 0; j--) {
        final Step curr = steps.get(j);
        final Axis axis = invertAxis(curr.axis);
        if(axis == null) break;

        if(j == 0) {
          if(this instanceof RelativeLocationPath || axis == Axis.PARENT) {
            invPath.steps.add(Axis.get(axis, TestNode.NODE));
          } else {
            indexMatch = false;
          }
        } else {
          final Step prev = steps.get(j - 1);
          if(prev.preds.size() != 0) break;
          invPath.steps.add(Axis.get(axis, prev.test));
        }
        steps.remove(j);
      }

      int predlength = preds.size() - oldPreds.size;
      if(indexMatch || invPath.steps.size() != 0) predlength += 1;

      final Preds newPreds = new Preds();
      if(!indexMatch && invPath.steps.size() != 0) newPreds.add(invPath);

      for(int p = 0; p != step.preds.size(); p++) {
        if(!oldPreds.contains(p)) newPreds.add(step.preds.get(p));
      }
      result = new InterSect(new Expression[] { indexArg }).compile(ctx);

      // add rest of predicates
      if(newPreds.size() != 0) result =
        new Filter(result, newPreds).compile(ctx);

      // add match with initial nodes
      //if(indexMatch && checkMatch(invPath)) {
      if(indexMatch) result = new IndexMatch(this, result, invPath);
      
      // add rest of location path
      if(oldPath.steps.size() != 0) result = new Path(result, oldPath);
    }
    return result;
  }
  
  /*
   * Check if the inverted path needs to be matched.
   * @param path location path
   * @return result of check
  private boolean checkMatch(final LocPath path) {
    if(path.steps.size() != 1) return true;
    final Step step = path.steps.get(0);
    return !step.simple(Axis.ANC) && !step.simple(Axis.ANCORSELF);
  }
   */

  @Override
  public final boolean sameAs(final Expression cmp) {
    if(!(cmp instanceof LocationPath)) return false;
    return steps.sameAs(((LocationPath) cmp).steps);
  }

  @Override
  public final boolean usesSize() {
    return false;
  }

  @Override
  public final boolean usesPos() {
    return false;
  }

  /**
   * Limit evaluation of predicates to first hit when only existence of path has
   * to be checked...
   * @param ctx query context
   */
  public final void addPosPred(final XPContext ctx) {
    if(steps.size() != 0 && steps.last().addPosPred()) {
      ctx.compInfo(OPTPOSPRED1);
    }
  }
  
  /**
   * Checks if the path is indexable.
   * @param ctx query context
   * @param exp expression which must be a literal
   * @param cmp comparator
   * @return result of check
   */
  public final Index.TYPE indexable(final XPContext ctx, final Expression exp,
      final Comp cmp) {

    if(!(this instanceof RelativeLocationPath && exp instanceof Literal)) return null;

    final Data data = ctx.local.data;
    final boolean txt = data.meta.txtindex && cmp == Comp.EQ;
    final boolean atv = data.meta.atvindex && cmp == Comp.EQ;
    final boolean wrd = data.meta.wrdindex && cmp == Comp.WORD;
    
    final Step step = steps.last();
    final boolean text = (txt || wrd) && step.test == TestNode.TEXT &&
      step.preds.size() == 0;
    final boolean attr = atv && step.simpleName(Axis.ATTR, false) !=
      Integer.MIN_VALUE;
    if(!text && !attr || !checkAxes()) return null;

    return attr ? Index.TYPE.ATV : wrd ? Index.TYPE.WRD : Index.TYPE.TXT;
  }

  /**
   * Checks if the specified location step has suitable index axes.
   * @return true result of check
   */
  public final boolean checkAxes() {
    for(int s = 0; s < steps.size() - 1; s++) {
      final Step curr = steps.get(s);
      // not the last text step
      if(curr.preds.size() != 0 || curr.axis != Axis.ANC
          && curr.axis != Axis.ANCORSELF && curr.axis != Axis.DESC
          && curr.axis != Axis.SELF && curr.axis != Axis.DESCORSELF
          && curr.axis != Axis.CHILD && curr.axis != Axis.PARENT) return false;
    }
    return true;
  }

  /**
   * Inverts a location path.
   * @param curr current location step
   * @return inverted path
   */
  public final LocationPath invertPath(final Step curr) {
    // hold the steps to the end of the inverted path
    final LocationPath path = new RelativeLocationPath();
    final Steps stps = steps;

    // add inverted pretext steps
    Axis lastAxis = invertAxis(stps.last().axis);
    for(int k = stps.size() - 2; k >= 0; k--) {
      final Step step = stps.get(k);
      final Step inv = Axis.get(lastAxis, step.test, step.preds);
      lastAxis = invertAxis(step.axis);
      path.steps.add(inv);
    }
    path.steps.add(Axis.get(lastAxis, curr.test));
    return path;
  }

  /**
   * Inverts an XPath axis.
   * @param axis axis to be inverted.
   * @return inverted axis
   */
  private static Axis invertAxis(final Axis axis) {
    switch(axis) {
      case ANC:        return Axis.DESC;
      case ANCORSELF:  return Axis.DESCORSELF;
      case ATTR:
      case CHILD:      return Axis.PARENT;
      case DESC:       return Axis.ANC;
      case DESCORSELF: return Axis.ANCORSELF;
      case PARENT:     return Axis.CHILD;
      case SELF:       return Axis.SELF;
      default:         return null;
    }
  }
}

